class Solution:
    def minDepth(self, root: TreeNode) -> int:
        if not root: return 0
        elif not root.left: return self.minDepth(root.right) + 1
        elif not root.right: return self.minDepth(root.left) + 1
        else: return min(self.minDepth(root.left),self.minDepth(root.right)) + 1
'''
递归的思路没看懂！！！
非递归方法
'''
class Solution:
    def minDepth(self, root: TreeNode) -> int:
        if not root:
            return 0

        ans = float('inf')
        stack = [(root, 0)]

        while stack:
            node, depth = stack.pop()
            if not node.left and not node.right:
                ans = min(ans, depth + 1)
            if node.left: stack.append((node.left, depth + 1))
            if node.right: stack.append((node.right, depth + 1))

        return ans
